﻿/*
题目: 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

https://leetcode.cn/problems/sliding-window-maximum/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 滑动窗口 + 单调栈(递减栈)
        int left = 0;
        deque<int> deq;
        vector<int> res;

        for (int i = 0; i < k; i++) {
            while (!deq.empty() && nums[deq.back()] < nums[i]) {
                deq.pop_back();
            }

            deq.push_back(i);
        }

        res.push_back(nums[deq.front()]);

        for (int i = k; i < nums.size(); i++) {
            // 维护单调栈
            while (!deq.empty() && nums[deq.back()] < nums[i]) {
                deq.pop_back();
            }

            // 排除出界的
            while (!deq.empty() && i - deq.front() >= k) {
                deq.pop_front();
            }
            deq.push_back(i);

            res.push_back(nums[deq.front()]);
        }

        return res;
    }
};